# 《合并区间》
# 原题链接：https://leetcode.cn/leetbook/read/array-and-string/c5tv3/

# 需求分析：
# 1、以数组 intervals 表示若干个区间的集合，
# 2、其中单个区间为 intervals[i] = [starti, endi] 。
# 3、合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

# 示例 1：
# 输入：intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
# 输出：[[1, 6], [8, 10], [15, 18]]
# 解释：区间[1, 3] 和[2, 6] 重叠, 将它们合并为[1, 6].

# 示例 2：
# 输入：intervals = [[1, 4], [4, 5]]
# 输出：[[1, 5]]
# 解释：区间[1, 4] 和[4, 5] 可被视为重叠区间。

# 提示：
# 1 <= intervals.length <= 104
# intervals[i].length == 2
# 0 <= starti <= endi <= 104

# 思路：先排序后比较，重叠则合并
class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()        # 升序排列 待合并区间集
        merged = [intervals[0]] # 初始化   已合并区间集
        # 定义比较函数：
        #     传入两个区间 A（左区间）B（右区间）
        #     重叠（不独立）则合并区间且返回Fals，不重叠（独立）则返回True
        #     由于排序后：A.start <= B.start 恒成立，所以只考虑区间向右扩张
        def compare(intervalA:List[int], intervalB:List[int]) -> List[int]:
            if intervalA[1] < intervalB[0]:   # A∩B = ∅
                return 1
            elif intervalA[1] < intervalB[1]: # A⊈B
                intervalA[1] = intervalB[1]
                return 0
            else:                             # B⊆A    
                return 0
        # 循环比较：
        #     区间独立则添加新的独立区间到区间集
        #     区间重叠则由比较函数处理合并区间
        #     当intervals遍历完，则区间集 合并完毕
        i,j = 0,1
        while j<len(intervals):
            if compare(merged[i], intervals[j]):
                merged.append(intervals[j])
                i += 1
            j += 1
        return merged